# include<iostream>

template<typename DT>
class DoubleLinkedList
{
private:
    struct Node
    {
        DT data;
        Node *prev;
        Node *next;

        Node(const DT & d=DT{}, Node *p=nullptr, Node *n=nullptr):
        data{d}, prev{p}, next{n}{}

        Node( DT && d, Node *p=nullptr, Node *n=nullptr):
        data{std::move(d)}, prev{p}, next{n}{}
    };

    
public:
    class const_iterator
    {
    public:
        const_iterator(): current{nullptr}
        {}

        const DT & operator* () const
        { return retrieve(); }

        const_iterator & operator++ ()
        {
            current = current->next;
            return *this;
        }

        const_iterator operator++ (int)
        {
            const_iterator old = *this;
            ++(*this);
            return old;
        }

        bool operator == (const const_iterator & rhs) const
        { return current == rhs.current; }

        bool operator != (const const_iterator & rhs) const
        { return !( *this == rhs); }

    protected:

        Node *current;

        DT & retrieve() const
        { return current->data; }

        const_iterator( Node *p  ) : current{p}
        {}

        friend class DoubleLinkedList<DT>;

    };

    class iterator: public const_iterator
    {
    public:
        iterator()
        {}

        DT & operator* ()
        { return const_iterator::retrieve(); }

        const DT & operator*() const
        { return const_iterator::operator*(); }

        iterator & operator++ ()
        {
            this->current = this -> current -> next;
            return *this;
        }

        iterator operator++(int)
        {
            iterator old = *this;
            ++(*this);
            return old;
        }
        

    protected:
        iterator(Node *p) : const_iterator{p}
        {}

        friend class DoubleLinkedList<DT>;

    };
    
public:

    DoubleLinkedList()
    {
        init();
    }
    DoubleLinkedList(const DoubleLinkedList & rhs)
    {
        init();
        for(auto & x : rhs)
            push_back(x);
    }
    ~DoubleLinkedList()
    {
        clear();
        delete head;
        delete tail;
    }
    DoubleLinkedList & operator=(const DoubleLinkedList & rhs)
    {
        DoubleLinkedList copy = rhs;
        std::swap(*this, copy);
        return *this;
    }
    DoubleLinkedList(DoubleLinkedList && rhs)
    : theSize{rhs.theSize}, head{rhs.head}, tail{rhs.tail}
    {
        rhs.theSize = 0;
        rhs.head = nullptr;
        rhs.tail = nullptr;
    }
    DoubleLinkedList & operator= (DoubleLinkedList && rhs)
    {
        std::swap(theSize, rhs.theSize);
        std::swap(head, rhs.head);
        std::swap(tail, rhs.tail);
        return *this;
    }
    
    iterator begin()
    {return { head -> next };}
    const_iterator begin() const
    {return { head -> next };}
    iterator end()
    {return { tail };}
    const_iterator end() const
    {return { tail };}

    int size() const
    {return theSize;}
    bool empty() const
    {return size() == 0;}

    void clear()
    {
        while( !empty() )
        pop_front();
    }
    
    DT & front()
    {return *begin();}
    const DT & front() const
    {return *begin();}
    DT & back()
    {return *--end();}
    const DT & back() const
    {return *--end();}
    void push_front( const DT & x)
    {insert(begin(), x);}
    void push_front( DT && x)
    {insert(begin(), std::move(x));}
    void push_back(const DT & x)
    {insert(end(), x);}
    void push_back(DT && x)
    {insert(end(), std::move(x));}
    void pop_front()
    {erase(begin());}
    void pop_back()
    {erase(--end());}

    iterator insert(iterator itr, const DT & x)
    {
        Node *p = itr.current;
        theSize++;
        return{p->prev = p->prev->next = new Node{x, p->prev, p}};
    }
    iterator insert(iterator itr, DT && x)
    {
        Node *p = itr.current;
        theSize++;
        return {p->prev = p->prev->next = new Node{std::move(x), p->prev, p}};
    }

    iterator erase(iterator itr)
    {
        Node *p = itr.current;
        iterator retVal{p->next};
        p->prev->next = p->next;
        p->next->prev = p->prev;
        delete p;
        theSize--;

        return retVal;
    }
    iterator erase(iterator from, iterator to)
    {
        for(iterator itr = from; itr!= to;)
            itr = erase(itr);

        return to;
    }
    void printList()
    {
        for (Node* it = head; it != nullptr; it = it->next)
            std::cout << it->data << "\t";
        std::cout << "\b" << std::endl; 
    }
   
   

private:
    int theSize;
    Node *head;
    Node *tail;

    void init()
    {
        theSize = 0;
        head = new Node;
        tail = new Node;
        head->next = tail;
        tail->prev = head;
    }
};
